package io.github.hadyang.leetcode.random;

import com.google.common.collect.Lists;
import org.junit.Test;

import java.util.*;

/**
 * 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
 *
 * <p>说明：
 *
 * <p>分隔时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。
 *
 * <p>示例 1：
 *
 * <p>输入: s = "catsanddog" wordDict = ["cat", "cats", "and", "sand", "dog"]
 *
 * <p>输出: [   "cats and dog",   "cat sand dog" ]
 *
 * <p>示例 2：
 *
 * <p>输入: s = "pineapplepenapple" wordDict = ["apple", "pen", "applepen", "pine", "pineapple"] 输出: [
 *   "pine apple pen apple",   "pineapple pen apple",   "pine applepen apple" ] 解释: 注意你可以重复使用字典中的单词。
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/word-break-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author haoyang.shi
 * @date 2019-10-21
 */
public class Q140 {

  public List<String> wordBreak(String s, List<String> wordDict) {
    Map<String, List<String>> map = new HashMap<>();
    boolean[] p = new boolean[s.length() + 1];

    p[0] = true;
    for (int i = 1; i <= s.length(); i++) {
      String sub = s.substring(0, i);
      for (int j = 0; j <= i; j++) {
        String word = s.substring(j, i);
        if (p[j] && wordDict.contains(word)) {
          p[i] = true;

          List<String> pres;
          if ((pres = map.get(sub)) == null) {
            pres = new ArrayList<>();
            map.put(sub, pres);
          }
          pres.add(word);
        }
      }
    }

    if (!p[s.length()]) {
      return Collections.emptyList();
    }

    List<String> resList = new LinkedList<>();
    p(map, resList, new ArrayList<>(), s);

    return resList;
  }

  private void p(Map<String, List<String>> map, List<String> res, List<String> cache, String s) {
    List<String> pres = map.get(s);

    for (String pre : pres) {
      int size = cache.size();
      cache.add(pre);

      if (pre.equals(s)) {
        StringJoiner joiner = new StringJoiner(" ");
        for (int i = cache.size() - 1; i >= 0; i--) {
          joiner.add(cache.get(i));
        }
        res.add(joiner.toString());
        cache.remove(size);
        continue;
      }
      p(map, res, cache, s.substring(0, s.length() - pre.length()));
      cache.remove(size);
    }
  }

  @Test
  public void test() {
    List<String> dict = Lists.newArrayList("cats", "dog", "sand", "and", "cat");
    System.out.println(wordBreak("catsanddog", dict));
  }
}
